//
// Created by 党清浩 on 2021/11/8.
//

#include <stdio.h>
#include <malloc.h>
#include <string.h>

#define N 20
#define M 2*N-1

typedef struct {
    //节点的权值
    int weight;
    //双亲的下标
    int parent;
    //左孩子的节点的下标
    int LCHild;
    //右孩子的节点的下标
    int RCHild;
} HTNode, HuffmanTree[M + 1];

typedef char *HuffmanCode[N + 1];

void CrtHuffmanTree(HuffmanTree ht, int w[], int n);

void CrtHuffmanCode(HuffmanTree ht, HuffmanCode hc, int n);

void select(HuffmanTree ht, int n, int *s1, int *s2);

int main() {
    int n;
    int i;
    scanf("%d", &n);
    HuffmanTree ht;
    HuffmanCode hc;
    int w[n];
    for (i = 1; i <= n; i++) {
        scanf("%d", &w[i]);
    }
    CrtHuffmanTree(ht, w, n);
    printf("HuffmanTree is:\n");
    for (i = 1; i <= (2 * n - 1); i++) {
        printf("%d:%d %d %d %d\n", i, ht[i].weight, ht[i].parent, ht[i].LCHild, ht[i].RCHild);
    }
    CrtHuffmanCode(ht, hc, n);
    printf("The Code is:\n");
    for (i = 1; i <= n; i++) {
        printf("%d:%s\n", ht[i].weight, hc[i]);
    }

    return 0;
}

void CrtHuffmanTree(HuffmanTree ht, int w[], int n) {
    int i;
    int m;
    int s1, s2;
    for (i = 1; i <= n; i++) {
        ht[i].weight = w[i];
        ht[i].parent = 0;
        ht[i].LCHild = 0;
        ht[i].RCHild = 0;
    }
    m = 2 * n - 1;
    for (i = n + 1; i <= m; i++) {
        ht[i].weight = 0;
        ht[i].parent = 0;
        ht[i].LCHild = 0;
        ht[i].RCHild = 0;
    }
    for (i = n + 1; i <= m; i++) {
        select(ht, i - 1, &s1, &s2);
        ht[i].weight = ht[s1].weight + ht[s2].weight;
        ht[s1].parent = i;
        ht[s2].parent = i;
        ht[i].LCHild = s1;
        ht[i].RCHild = s2;
    }

}

void select(HuffmanTree ht, int n, int *s1, int *s2) {
    int i;
    int min1 = 100;
    int min2 = 100;
    for (i = 1; i <= n; i++) {
        if (ht[i].parent == 0 && min1 > ht[i].weight) {
            min1 = ht[i].weight;
            *s1 = i;
        }
    }
    for (i = 1; i <= n; i++) {
        if (i != (*s1) && ht[i].parent == 0) {
            if (min2 > ht[i].weight) {
                min2 = ht[i].weight;
                *s2 = i;
            }
        }
    }
}


void CrtHuffmanCode(HuffmanTree ht, HuffmanCode hc, int n) {
    int i;
    int c;
    int p;
    int start;
    char *cd;
    cd = (char *) malloc(n * sizeof(char));
    cd[n - 1] = '\0';
    for (i = 1; i <= n; i++) {
        start = n - 1;
        c = i;
        p = ht[i].parent;
        while (p != 0) {
            --start;
            if (ht[p].LCHild == c) cd[start] = '0';
            else cd[start] = '1';
            c = p;
            p = ht[p].parent;
        }
        hc[i] = (char *) malloc((n - start) * sizeof(char));
        strcpy(hc[i], &cd[start]);
    }
    free(cd);
}
